Internet Info 1993

home *** CD-ROM | disk | FTP | other *** search

/ Internet Info 1993 / Internet Info CD-ROM (Walnut Creek) (1993).iso / inet / ien / ien-164 < prev next >

Wrap

Text File | 1988-12-01 | 38.9 KB | 1,416 lines

CMOS SYSTEM OVERVIEW Jerry Stern, Greg Ruth, and Jack Haverty Bolt Beranek and Newman Inc. January 12, 1981 Stern, Ruth, and Haverty -1- Version 1.0 IEN 164 January 1981 Preliminary Table of Contents 1 Introduction.......................................... 2 2 General Design Considerations......................... 3 3 Process Management.................................... 5 4 Interprocess Communication............................ 5 5 Input/Output.......................................... 6 6 Memory Allocation..................................... 7 7 System Clock.......................................... 8 8 Software Development Tools............................ 8 9 Future Development.................................... 8 10 CMOS System Calls.................................... 9 11 System Generation................................... 19 Stern, Ruth, and Haverty -i- Version 1.0 IEN 164 January 1981 Preliminary 1 Introduction CMOS is a multiprogrammed real-time operating system for BBN's C-machines. It is essentially a reimplementation of MOS, (1) a PDP-11 operating system developed by SRI. Whereas MOS is written in Macro-11 assembly language, CMOS is written in C. (2) Programming support for CMOS is provided by the UNIX operating system. CMOS itself, as well as program modules written to run as CMOS processes, are edited and compiled on the UNIX operating system, and object modules are loaded into the target machine. Since both the development and target machines support C-based code, it is also feasible to do some initial debugging in the time-shared environment. CMOS is a small, simple operating system that provides the following basic features: - multiple processes - interprocess communication/coordination - asynchronous I/O - memory allocation - system clock management. CMOS development was motivated by the desire to produce a C-machine operating system suitable for use in communications- oriented applications. In light of favorable experience with MOS, it was decided to adapt a version of MOS for the C-machine. The choice of C as a system programming language was dictated by the specific nature of the C-machine. The C-machine is a microprogrammed, 20-bit machine which has an architecture explicitly designed to support the C language. The C-machine comes in two models: the C/50, which has a 1-megabyte (1 "byte" = 10 bits) physical address space and no memory management; and the C/70, which has a 2-megabyte address space and memory management. Versions of CMOS have been developed for both of these machines, as well as for the LSI-11 and the Z8000. _______________ (1) Kunzelman, R. C., J. E. Mathis, and D. L. Retz, "Progress Report on Packet Radio Experimental Network, Quarterly Technical Report No. 8." (2) Kernighan, B. W. and D. M. Ritchie, "The C Programming Language", Prentice-Hall, Inc., 1978. Stern, Ruth, and Haverty -2- Version 1.0 IEN 164 January 1981 Preliminary It should be noted that, although CMOS is targeted for use in several applications, it has not yet been used anywhere and should be considered as still under development. One major motivation for the creation of CMOS was to provide an operating system for the C machines, for use in applications where the memory limitations make LSI-11 approaches unsuitable. Although CMOS will run on LSI-11s, this is not an intended use. CMOS systems may use processes which exceed the address space of the LSI-11 architecture, and can only be run on C-machines or other machines which support the needed memory. The important aspects of the CMOS design are described in the following sections. The final sections provide a detailed description of CMOS primitives and general system generation information. 2 General Design Considerations The design and programming of CMOS have been motivated by goals of style, clarity, and consistency rather than a desire to achieve ultimate efficiency. This is not to say that efficiency issues have been ignored. CMOS is quite compact and efficient by virtue of its simplicity. Design principles and programming practices have not been compromised, however, for the sake of saving every possible byte or cpu cycle. CMOS is designed to be an "open" operating system. This means that no distinct division exists between the operating system and the application program. One can view the operating system as a collection of library routines. The operating system can be easily extended by adding new routines and can be reduced by excluding unneeded routines. The programmer is not confined to the outermost interface presented by the operating system. If appropriate, the programmer can directly access lower-level interfaces. Although CMOS is intended primarily for C-machines, it is designed to be a portable operating system. The use of a high- level language is, of course, the principal factor in CMOS portability. Small size and simplicity are other important factors. The design attempts to minimize the amount of machine- dependent code and to segregate it into separate modules. The I/O system design allows for easy replacement of device-dependent modules. Versions of CMOS exist for the PDP-11 and the Z8000 computers. Stern, Ruth, and Haverty -3- Version 1.0 IEN 164 January 1981 Preliminary CMOS does not support either virtual memory or virtual address spaces. The entire system shares a single, physical address space. This lack of sophistication is due, in large part, to the nature of real-time systems. Programs and data must be continuously available in main memory in order to meet response-time requirements. Thus, virtual memory techniques such as swapping or paging are not suitable for real-time applications. The issue of virtual address spaces is more complicated. The most common reason for providing virtual address spaces in real-time systems is to overcome an architectural deficiency of the computer. Many computers have small address spaces, yet can support a much larger amount of physical memory. Therefore, multiple address spaces are required to take advantage of larger memory sizes. The C-machines do not suffer from this architectural defect. The C/50 provides a one-megabyte address space and the C/70 twice that. This is sufficient for all currently envisioned CMOS applications. For this reason, the current CMOS does not need, and does not support, virtual address spaces. For other machines (e.g., the PDP-11), address space limitations are more severe. On these machines, CMOS may be limited to a class of smaller applications. Other applications may motivate further extensions to CMOS, to introduce process isolation using memory mapping, dynamic process creation, preemption, or other additions to the basic functionality. The use of a single address space gives CMOS several important advantages over multiple address space systems. First, the single address space is a major contributing factor to the overall simplicity of CMOS. Not only is the operating system relieved of address space management chores, but also, programming and debugging are generally facilitated. Second, data sharing among processes is direct, convenient, and efficient. In multiple address space systems, memory sharing is often a difficult problem. Third, I/O devices have direct access to all of memory. In multiple address space systems, I/O devices are typically restricted to a single address space. This often produces a need for extra data copying, especially in connection with DMA devices. Fourth, an entire CMOS system is linked together as one composite program. This means that non-identical processes can still share a single copy of common subroutines. Multiple address space systems usually cannot match this level of code-space efficiency. The large address space provided by CMOS obviates the need to artificially split systems into a number of Stern, Ruth, and Haverty -4- Version 1.0 IEN 164 January 1981 Preliminary processes because of the address space limitations. 3 Process Management CMOS processes are defined at compilation time. They cannot be dynamically created or destroyed during system operation. For each process, a set of basic attributes is specified including a name, an initial program entrypoint, and a stack size. CMOS employs a rudimentary process scheduling method. Three process states are defined: (1) running; (2) ready to run; and (3) waiting for an event. A running process always runs to completion. This means that the processor is relinquished only by explicit action of the running process. It is never taken away by the operating system. There is no time-slicing or other form of preemption. The next process to run is selected by a simple round-robin algorithm. All processes have a uniform scheduling priority. This non-preemptive scheduling discipline has important implications. First, processes must be designed not to monopolize the processor for long time periods. Otherwise, crucial tasks may fail to be serviced in a timely fashion. Second, critical program sections (i.e., program sections that can be safely entered by only one process at a time) need no explicit protection. The absence of preemption guarantees the integrity of critical program sections. Interrupt handling creates a separate class of critical sections that are not protected by the scheduling discipline. These critical sections exist only within the operating system and are of no concern to application programs. CMOS protects these critical sections in the standard manner (viz., by temporarily disabling interrupts). 4 Interprocess Communication CMOS processes communicate with one another by passing messages known as "events". For this purpose, the operating system provides primitives called "signal", "wait", and "recv". The signal primitive permits a process to send an event to another process. The wait primitive permits a process to wait for an event that may or may not have arrived. The recv primitive permits a process to receive an event that has already arrived. Stern, Ruth, and Haverty -5- Version 1.0 IEN 164 January 1981 Preliminary An event message contains the sender process ID, an event ID, and one word of unspecified data. The event ID is used to indicate the type of event. Both the wait and receive primitives allow a process to select the event IDs of immediate interest. The meaning of the data word depends on the event type. It is quite common for the data word to contain a pointer to a larger data structure. CMOS provides a facility that helps to automate event processing activities. A process can designate a procedure to be the event handler for a particular event type. Thereafter, the event handler becomes active whenever a special wait primitive, called "waith", is invoked. For each event received, waith checks to see if an event handler has been defined. If so, the event handler procedure is automatically dispatched. This frees the caller of waith from the responsibility of having to deal with events not of direct interest. Processing of these events can be viewed as a background activity. 5 Input/Output CMOS provides an asynchronous I/O facility. To perform I/O, a process creates an I/O request block (IORB). The IORB identifies the target device, the type of operation (e.g., read, write, abort), and information relevant to the particular operation (e.g., buffer areas for data transfer). The IORB also specifies an event ID. To initiate processing, the IORB is passed to the operating system. When the request is completed, the operating system signals an event to the requesting process. The event message contains the event ID taken from the IORB and a data word that contains the address of the IORB. In this way, the requesting process can easily associate the completion event with the original request. Status information is returned in the IORB. A process can direct I/O to a specific device or to a special "primary" device. Primary devices are defined on a per- process basis and can be either assigned (to a specific device) or unassigned. If a process attempts to perform I/O on an unassigned primary device, the process is suspended until a primary device is assigned. This permits a single device to be moved from one process to another and thereby provides a simple way to share a terminal among several processes. The core of the CMOS I/O system is a device-independent module, "eior" (enter I/O request), that provides a centralized interface between the application program and the various device driver modules. As described above, this interface accepts IORBs from the application program. The IORBs are automatically queued Stern, Ruth, and Haverty -6- Version 1.0 IEN 164 January 1981 Preliminary on a per-device basis. If desired, requests from different processes can be interspersed for the same device. When a device becomes ready to accept the next request, the first IORB in the device queue, if any, is passed to the appropriate device driver module. All device driver modules provide a standardized interface expected by the core I/O system. This interface consists of four entrypoints: (1) a configuration entry; (2) an initialization entry; (3) a request entry; and (4) an interrupt handler entry. A system configuration table specifies the driver configuration entry for each device. During system initialization, the configuration entry is invoked to obtain the other three driver entrypoints, and the size of any per-device data base required by the driver. The initialization entry is invoked automatically before the first IORB is passed to the driver. The request and interrupt handler entries perform standard device control functions. At present, CMOS includes driver modules for asynchronous terminals and for 1822 network interfaces. 6 Memory Allocation CMOS includes routines that allocate and deallocate blocks of memory from a free storage pool. Both the operating system and the application program share a common pool. Three allocation options are available to control operating system behavior in the case of an allocation failure: (1) return an error code; (2) wait for more memory to become available; and (3) cease system operation. CMOS provides an allocation mechanism only, not an allocation policy. The policy, of course, is the responsibility of the application program. In practice, however, few application programs incorporate a memory allocation policy that eliminates the possibility of free space exhaustion. Instead, some applications include a recovery mechanism to deal with this problem. It is reasonable to expect that such a mechanism will depend upon the continued functioning of the operating system. Therefore, the operating system must not itself become immediately disabled as a result of free space exhaustion. To prevent disablement, CMOS depends on "reserve storage pools". A separate reserve storage pool is created for each type of object needed by a crucial function. The operating system uses two such pools, one for event messages and one for timer queue entries. Reserve storage pools are managed by special allocation and deallocation routines. The special allocation routine first attempts to obtain space from the common pool. If this fails, space is taken instead from the reserve pool and the Stern, Ruth, and Haverty -7- Version 1.0 IEN 164 January 1981 Preliminary caller is so informed. If the reserve pool is exhausted, the system dies. System primitives that use reserve storage pools return an indication of when reserve storage has been tapped. An application program can therefore detect free space exhaustion by this means or by the direct failure of a simple allocation request. At this point, the operating system will continue to function for a period of time (or number of calls) determined by reserve storage pool sizes. 7 System Clock CMOS provides a clock management facility that maintains a time-of-day clock and permits processes to set "alarms". An alarm is simply an event that is signalled by the clock manager after a specified time period has elapsed. Both the event ID and the data word of the event message are specified by the process that sets the alarm. An alarm can be either a one-time alarm or an interval alarm that is automatically repeated at regular intervals. 8 Software Development Tools All programming support for CMOS software development is now provided by the UNIX time-sharing system, via the UNIX C compiler and linker. BBN has developed a Version 7 UNIX and a C compiler/linker to run on the C-machines. The same hardware configuration of a C-machine can support both the UNIX and CMOS systems, although not simultaneously, of course. We plan to use the UNIX system development tools to create CMOS systems, which can then be run and tested by bootstrapping the CMOS code in place of UNIX on the same or different hardware. 9 Future Development There is a variety of possible extensions to CMOS, which take advantage of the increased flexibility provided by the hardware base. We intend to pursue these as specific applications arise which require additional functionality. Stern, Ruth, and Haverty -8- Version 1.0 IEN 164 January 1981 Preliminary The most interesting category of extensions involves the use of the memory mapping hardware available for C machines. In the standard C-machine configuration, the 20-bit address space provides access to a physical memory of 1 Mbyte. Within this physical address space, processes can share any or all of the memory, since the process address space is also 1 Mbyte. The memory mapper hardware extends the machine's capabilities in two ways. The first extension provides for support of 2 Mbytes of physical memory. Each process is, however, limited to 1 Mbyte of address space. The second extension lies in the ability of the memory map to support eight independent active process maps. This creates an environment in which processes can share portions of their address spaces with the system or other processes, with fast context switching between the eight active processes. This removes two of the basic limitations we have encountered in real-time designs based on PDP-11 architectures, namely, the granularity of memory sharing and the speed of context switching. The CMOS environment has not yet been extended to utilize these additional facilities, although we anticipate that this effort will begin soon. 10 CMOS System Calls This section describes CMOS system calls available to the application programmer. These calls are divided into two major groups, low-level functions and higher-level functions. The low-level functions correspond roughly to the MOS interface, and the higher-level functions provide certain additional capabilities. The usage of each system call is described in terms of the C language. Two typedefs are first defined and then referenced by a few of the system call descriptions. typedef struct { /* event message buffer */ char msevent; /* event ID */ char mssender; /* sender process ID */ int msdata; /* user data */ } MSG; Stern, Ruth, and Haverty -9- Version 1.0 IEN 164 January 1981 Preliminary typedef struct iorb { /* I/O request block */ struct iorb *irnextp; /* ptr to next IORB on chain */ int irdevid; /* device ID */ char irevent; /* completion signal event */ char irpid; /* requestor's process ID */ char *irbufp; /* buffer ptr */ char irport; /* port number of request */ char iropcode; /* operation code */ int irbufsiz; /* buffer size (in bytes) */ int irstatus; /* status of I/O operation */ int irnxfer; /* number of bytes transferred */ int irpad[2]; /* mysterious padding */ } IORB; Stern, Ruth, and Haverty -10- Version 1.0 IEN 164 January 1981 Preliminary LOW-LEVEL FUNCTIONS Process Attributes Name: getpid Function: convert process name to process ID Usage: pid = getpid (name) char name[]; /* process name to convert null name => calling process */ int pid; /* process ID for given name */ Name: getpn Function: convert process ID to process name Usage: pn = getpn (pid, namep) int pid; /* process ID to convert 0 => calling process */ char *namep; /* place to store name */ char *pn; /* same as namep */ Name: getprio Function: get primary I/O devices of specified process Usage: getprio (pid, priop) int pid; /* process ID, 0 => calling process */ struct { int idevid; /* primary input device ID */ int odevid; /* primary output device ID */ } *priop; Stern, Ruth, and Haverty -11- Version 1.0 IEN 164 January 1981 Preliminary Name: setprio Function: set primary I/O devices of specified process Usage: setprio (pid, idevid, odevid) int pid; /* process ID, 0 => calling process */ int idevid; /* input device ID, <0 => no change */ int odevid; /* output device ID, <0 => no change */ Name: movprio Function: move primary I/O devices of caller to another process Usage: movprio (pid) int pid; /* target process ID */ Device Attributes Name: getdid Function: convert device name to device ID Usage: devid = getdid (name) char name[]; /* device name to convert */ int devid; /* device ID */ Name: getdn Function: convert device ID to device name Usage: dn = getdn (devid, namep) int devid; /* device ID to convert */ char *namep; /* place to store name */ char *dn; /* same as namep */ Stern, Ruth, and Haverty -12- Version 1.0 IEN 164 January 1981 Preliminary Input/Output Name: eior Function: enter an I/O request Usage: ec = eior (iorbp) IORB *iorbp; /* I/O request block ptr */ int ec; /* error code */ Interprocess Communication Name: signal Function: signal an event to a process Usage: sw = signal (pid, event, data) char pid; /* target process ID */ char event; /* event number */ int data; /* data for target process */ int sw; /* 1 if reserve pool used to queue signal, else 0 */ Name: wait Function: wait for any event Usage: wait (msgp) MSG *msgp; /* ptr to message buffer */ Name: waits Function: wait for a single specified event Usage: waits (event, msgp) char event; /* desired event */ MSG *msgp; /* message buffer ptr */ Stern, Ruth, and Haverty -13- Version 1.0 IEN 164 January 1981 Preliminary Name: waitm Function: wait for one of multiple specified events Usage: waitm (evlist, nev, msgp); char *evlist; /* event list (array) */ int nev; /* number of events in list */ MSG *msgp; /* message buffer ptr */ Name: recv Function: receive any pending event Usage: sw = recv (msgp) MSG *msgp; /* ptr to message buffer */ int sw; /* 1 if event returned, else 0 */ Name: recvs Function: receive a single specified pending event Usage: sw = recvs (event, msgp) char event; /* desired event */ MSG *msgp; /* message buffer ptr */ int sw; /* 1 if event returned, else 0 */ Name: recvm Function: receive one of multiple specified pending events Usage: sw = recvm (evlist, nev, msgp); char *evlist; /* event list (array) */ int nev; /* number of events in list */ MSG *msgp; /* message buffer ptr */ int sw; /* 1 if event returned, else 0 */ Stern, Ruth, and Haverty -14- Version 1.0 IEN 164 January 1981 Preliminary Memory Allocation Name: alloc Function: allocate memory block, return if not available Usage: blkp = alloc (nbytes) int nbytes; /* size of block desired */ char *blkp; /* ptr to allocated block, else null */ Name: allocw Function: allocate memory block, wait if not available Usage: blkp = allocw (nbytes) int nbytes; /* size of block desired */ char *blkp; /* ptr to allocated block */ Name: allocd Function: allocate memory block, die if not available Usage: blkp = allocd (nbytes) int nbytes; /* size of block desired */ char *blkp; /* ptr to allocated block */ Name: free Function: free a previously allocated block Usage: free (blkp) char *blkp; /* ptr to block */ Stern, Ruth, and Haverty -15- Version 1.0 IEN 164 January 1981 Preliminary System Clock Management Name: alarm Function: set alarm to awaken process Usage: sw = alarm (event, data, delay) char event; /* signal event */ int data; /* signal data */ int delay; /* timeout period in seconds/60 */ int sw; /* 1 if reserve pool used to queue Name: ialarm Function: set alarm to awaken process at regular intervals Usage: sw = ialarm (event, data, interval) char event; /* signal event */ int data; /* signal data */ int interval; /* timeout interval in seconds/60 */ int sw; /* 1 if reserve pool used to queue Name: kalarm Function: kill any specified pending alarms Usage: kalarm (event, data) char event; /* event of requests to kill */ int data; /* data of requests to kill */ Name: setod Function: set time of day Usage: setod (time) long time; /* time of day */ Stern, Ruth, and Haverty -16- Version 1.0 IEN 164 January 1981 Preliminary Name: getod Function: get time of day Usage: time = getod () long time; /* time of day */ Stern, Ruth, and Haverty -17- Version 1.0 IEN 164 January 1981 Preliminary HIGHER-LEVEL FUNCTIONS Event Management Name: newev Function: generate a new event number, unique system-wide Usage: event = newev () char event; /* event number */ Name: setevh Function: associate an event handler routine with a specified event for this process Usage: oldent = setevh (event, entryp) char event; /* event to be handled */ int (*entryp) (); /* event handler entrypoint */ /* if null, cancel event handler */ int (*oldent) (); /* previous entryp, else null */ Name: waith Function: wait for an event; dispatch event handler if one is defined, else return. Usage: waith (msgp) MSG *msgp; /* ptr to message buffer */ Name: waitsh Function: wait for an event; dispatch event handler if one is defined; else return if event is the one specified; else ignore event; Usage: waitsh (event, msgp) char event; /* desired event */ MSG *msgp; /* message buffer ptr */ Stern, Ruth, and Haverty -18- Version 1.0 IEN 164 January 1981 Preliminary Synchronous Input/Output Name: read Function: read from a specified device; event handlers are active while awaiting read completion. Usage: nbytes = read (devid, bufp, bufsiz) int devid; /* device ID */ char *bufp; /* buffer ptr */ int bufsiz; /* buffer size */ int nbytes; /* number of bytes read */ Name: write Function: write to a specified device; event handlers are NOT active while awaiting write completion. Usage: nbytes = write (devid, bufp, bufsiz) int devid; /* device ID */ char *bufp; /* buffer ptr */ int bufsiz; /* buffer size */ int nbytes; /* number of bytes written */ 11 System Generation The following CMOS modules must be linked into any system configuration: cm_init Initialization routines. cm_data Process control and configuration tables. cm_util CMOS utilities. cm_err Error message routines. cm_proc Basic process management routines. cm_queue Queue manipulation routines. cm_ipc Interprocess communication routines. cm_mem Memory management primitives. Stern, Ruth, and Haverty -19- Version 1.0 IEN 164 January 1981 Preliminary cm_io Basic I/O routines. In addition to the required modules, the following optional modules may be included for specific hardware device support: cm_time Timer management routines. cm_tty Terminal driver routines (to be rewritten). cm_1822 1822 driver routines (to be written). cm_smd Disk driver routines (to be written). cm_mlc MLC driver routines (to be written). In order to include DDT the following modules must be included: ddt_main ddt_cmd ddt_code ddt_brk ddt_sym Stern, Ruth, and Haverty -20- Version 1.0 IEN 164 January 1981 Preliminary References 1. Mathis, J. and Klemba, K., "The Micro Operating System," Chapter 6 of Terminal Interface Unit Notebook, Vol. 2, SRI International, March 1980. <MOS reference> 2. Kraley, M. et al., "Design of a User-microprogrammable Building Block," Thirteenth Annual Workshop on Microprogramming, Colorado Springs, Colorado, 1980. 3. Ritchie, D.M. and Thompson, K., "The UNIX Time-Sharing System," Bell System Technical Journal 57(6) pp. 1905-1929 (1978). 4. Kernighan, B.W. and Ritchie, D.M., The C Programming Language, Prentice-Hall, Inc., 1978. Stern, Ruth, and Haverty -21- Version 1.0 IEN 164 January 1981 Preliminary APPENDIX CMOS Error Messages (C-machine version) cvdevnm: Device not found The mate specified for a device (in the device control table initialization data) is not the name of any existing device. getdcte: Bad device ID The CMOS primitive (e.g. eior, getdn) was called with an invalid device id. dlvrmsg: NULL msg ptr Due to an internal error (blush). mkroom: Memory full Insufficient space in the free memory pool to accommodate device driver data and/or process stacks during system initialization. alloc: Invalid request The CMOS primitive "alloc" has been called with a negative block size. free: Invalid addr The CMOS primitive "free" has been called with a pointer outside the free memory pool. allocd: Allocation failed An allocation request via the CMOS primitive "allocd" has failed. plalloc: Pool empty The reserve memory pool has been exhausted. Stern, Ruth, and Haverty -22- Version 1.0 IEN 164 January 1981 Preliminary dschd: Stack overflow A process has overrun its stack. This may be due to an excessive depth of nested procedure calls. The only solution is to reassemble the system with more stack space. getpcte: Bad pid A CMOS primitive was called with a non-existent process id. mktqe: Bad delay time A CMOS clock management primitive was given a timeout period of 0 by the caller. In addition, there are various fatal conditions trapped by CMOS: TRAP: invalid memory addr TRAP: illegal instruction TRAP: illegal micro call TRAP: privileged operation TRAP: register overflow TRAP: EDAC error TRAP: register underflow For every trap the following machine status values are printed out: PC = program counter PS = program status SP = stack pointer Stern, Ruth, and Haverty -23- Version 1.0